package com.laivi.basic.module.algorithm;

import java.util.BitSet;

import com.laivi.basic.util.ArrayUtil;

public class Sorts {
	//*********************************************位排序****************************************
	public void bitSort(int bitLength,int[] datas){
		BitSet set=new BitSet(bitLength);
		for(int data:datas){
			set.set(data,true);
		}
		int k=0;
		for(int i=0;i<bitLength;i++){
			if(set.get(i)){
				datas[k++]=i;
			}
		}
	}
	//*********************************************快速排序****************************************
	private <T extends Comparable<T>> void quickSort(T[] datas,int start,int end){
		if(start>=0 && start <end && end<datas.length){
			int i=start;
			int j=end;
			T k=datas[start];
			int position=start;
			while(i<j){
				while(j>=0 && datas[j].compareTo(k)>0){
					j--;
				}
				if(j<i){
					break;
				}
				datas[position]=datas[j];
				position=j;
				while(i<datas.length && datas[i].compareTo(k)<=0){
					i++;
				}
				if(j<i){
					break;
				}
				datas[position]=datas[i];
				position=i;
			}
			datas[position]=k;
			quickSort(datas,start,position-1);
			quickSort(datas,position+1,end);
		}
	}
	
	public <T extends Comparable<T>> void quickSort(T[] datas){
		quickSort(datas,0,datas.length-1);
	}
	
	//*********************************************冒泡排序****************************************
	public <T extends Comparable<T>> void bulbSort(T[] datas){
		for(int i=datas.length-1;i>=0;i--){
			for(int j=0;j<i;j++){
				if(datas[j].compareTo(datas[j+1])>0){
					ArrayUtil.swap(datas,j,j+1);
				}
			}
		}
	}
	
	//*********************************************选择排序****************************************
	public <T extends Comparable<T>> void choiceSort(T[] datas){
		for(int i=datas.length-1;i>=0;i--){
			for(int j=0;j<i;j++){
				if(datas[j].compareTo(datas[i])>0){
					ArrayUtil.swap(datas,i,j);
				}
			}
		}
	}
	
	//*********************************************归并排序****************************************
	private <T extends Comparable<T>> void inSort(T[] datas,int start,int end){
		for(int i=start;i<end;i++){
			if((i+1)<datas.length && datas[i].compareTo(datas[i+1])>0){
				ArrayUtil.swap(datas,i,i+1);
			}else{
				break;
			}
		}
	}
	
	private <T extends Comparable<T>> void meger(T[] datas,int start,int mid,int end){
		int i=start;
		int j=mid+1;
		while(i<=mid && j<datas.length){
			if(datas[i].compareTo(datas[j])>0){
				ArrayUtil.swap(datas,i,j);
			}
			i++;
			inSort(datas,j,end);
		}
	}
	
	private <T extends Comparable<T>>  void megerSort(T[] datas,int start,int end){
		if(start<end){
			int mid=(start+end)/2;
			megerSort(datas,start,mid);
			megerSort(datas,mid+1,end);
			meger(datas,start,mid,end);
		}
	}
	
	public <T extends Comparable<T>> void megerSort(T[] datas){
		megerSort(datas,0,datas.length);
	}
	
	//*********************************************堆排序****************************************
	private <T extends Comparable<T>> void maxHeapify(T[] datas,int i,int heapSize){
		int l=2*i+1;					//left
		int r=2*(i+1);					//right
		int largest=i;
		if(l<=heapSize && datas[l].compareTo(datas[i])>0){
			largest=l;
		}
		if(r<=heapSize && datas[r].compareTo(datas[largest])>0){
			largest=r;
		}
		
		if(largest!=i){
			ArrayUtil.swap(datas,i,largest);
			maxHeapify(datas,largest,heapSize);
		}
	}
	
	public <T extends Comparable<T>> void buildMaxHeap(T[] datas){
		int heapSize=datas.length-1;
		for(int i=datas.length/2;i>=0;i--){
			maxHeapify(datas,i,heapSize);
		}
	}
	
	public <T extends Comparable<T>> void heapSort(T[] datas){
		buildMaxHeap(datas);
		int heapSize=datas.length-1;
		for(int i=datas.length-1;i>=1;i--){
			ArrayUtil.swap(datas,0,i);
			heapSize=heapSize-1;
			maxHeapify(datas,0,heapSize);
		}
	}
}